<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
<meta name="viewport"
      content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">

    <meta name="author" content="kissdata">


    <meta name="subtitle" content="人生笔记">


    <meta name="description" content="南邮计算机学院2021毕业生王鹏的介绍，cs软件工程专业">


    <meta name="keywords" content="wangpeng 王鹏 南邮 南京">


<title>简答题-数据结构 | 王鹏的小岛</title>



    <link rel="icon" href="/myIcon.ico">




    <!-- stylesheets list from _config.yml -->
    
    <link rel="stylesheet" href="/css/style.css">
    



    <!-- scripts list from _config.yml -->
    
    <script src="/js/script.js"></script>
    
    <script src="/js/tocbot.min.js"></script>
    



    
    
        <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
    });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
        src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML">
</script>


    


<meta name="generator" content="Hexo 7.0.0"></head>

<body>
    <script>
        // this function is used to check current theme before page loaded.
        (() => {
            const currentTheme = window.localStorage && window.localStorage.getItem('theme') || '';
            const isDark = currentTheme === 'dark';
            const pagebody = document.getElementsByTagName('body')[0]
            if (isDark) {
                pagebody.classList.add('dark-theme');
                // mobile
                document.getElementById("mobile-toggle-theme").innerText = "· Dark"
            } else {
                pagebody.classList.remove('dark-theme');
                // mobile
                document.getElementById("mobile-toggle-theme").innerText = "· Light"
            }
        })();
    </script>

    <div class="wrapper">
        <header>
    <nav class="navbar">
        <div class="container">
            <div class="navbar-header header-logo"><a href="/">侠之大者</a></div>
            <div class="menu navbar-right">
                
                    <a class="menu-item" href="/update/mystate">Career</a>
                
                    <a class="menu-item" href="/category">Legend</a>
                
                    <a class="menu-item" href="/about">Me</a>
                
                <input id="switch_default" type="checkbox" class="switch_default">
                <label for="switch_default" class="toggleBtn"></label>
            </div>
        </div>
    </nav>

    
    <nav class="navbar-mobile" id="nav-mobile">
        <div class="container">
            <div class="navbar-header">
                <div>
                    <a href="/">侠之大者</a><a id="mobile-toggle-theme">·&nbsp;Light</a>
                </div>
                <div class="menu-toggle" onclick="mobileBtn()">&#9776; Menu</div>
            </div>
            <div class="menu" id="mobile-menu">
                
                    <a class="menu-item" href="/update/mystate">Career</a>
                
                    <a class="menu-item" href="/category">Legend</a>
                
                    <a class="menu-item" href="/about">Me</a>
                
            </div>
        </div>
    </nav>

</header>
<script>
    var mobileBtn = function f() {
        var toggleMenu = document.getElementsByClassName("menu-toggle")[0];
        var mobileMenu = document.getElementById("mobile-menu");
        if(toggleMenu.classList.contains("active")){
           toggleMenu.classList.remove("active")
            mobileMenu.classList.remove("active")
        }else{
            toggleMenu.classList.add("active")
            mobileMenu.classList.add("active")
        }
    }
</script>
            <div class="main">
                <div class="container">
    <article class="post-wrap page">
        
        <h2 class="post-title">简答题-数据结构</h2>
        
        <section class="post-content">
            <p>[TOC]</p>
<h2 id="一、二叉树"><a href="#一、二叉树" class="headerlink" title="一、二叉树"></a>一、二叉树</h2><ol>
<li>已知某二叉树的先序遍历序列为 <strong>ABC∅∅DE∅G∅∅F∅H∅∅∅</strong>，这里的 <code>∅</code> 表示空子树。要求：（1）[5分] 画出此二叉树，用  <code>∅</code> 表示空子树。（2）[5分] 根据所画出的二叉树，写出中序遍历。</li>
</ol>
<p>答: （1）先序遍历是从树的根开始画，最终图</p>
<p><img src="/image/algo/q1_porder.png"></p>
<p>（2）中序遍历是根在中间，从左子树开始。答案 <code>∅C∅B∅E∅G∅D∅F∅H∅A∅</code></p>
<p><strong>Note:</strong> 先序遍历 “根-左-右”，中序遍历 “左-根-右”，后序遍历是 “左-右-根”。</p>
<h2 id="二、图"><a href="#二、图" class="headerlink" title="二、图"></a>二、图</h2><ol start="2">
<li>图是一个<strong>无向图</strong>，有 6 个顶点 ① ~ ⑥。要求：（1）[2分] 给出顶点 ① 的度。（2）画出它的邻接矩阵。</li>
</ol>
<p>   <img src="/image/algo/q2_ev.png"></p>
<p>答：参考《算法(第4版)》<code>P331</code>、<code>P335</code></p>
<p>（1）某个顶点的 <strong>度数</strong> 即为依附于它的边的总数。所以顶点 ① 的度是 <u> 2 </u>。</p>
<p>（2）邻接矩阵是 6×6 的布尔矩阵，如果两个点有相连的边就填 1 ，没有就填 0。结果：</p>
<p><img src="/image/algo/q2_answer.png"></p>
<p><strong>Notes:</strong> 在C语言里邻接矩阵一般这样定义</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">    <span class="type">int</span> **a;    <span class="comment">// 链接表, 二维数组表示</span></span><br><span class="line">    <span class="type">int</span> V;      <span class="comment">// 顶点数目</span></span><br><span class="line">    <span class="type">int</span> E;      <span class="comment">// 边的数目</span></span><br><span class="line">    <span class="type">int</span> noEdge; <span class="comment">// 两个顶点间无边时填的值</span></span><br><span class="line">&#125;mGraph;</span><br></pre></td></tr></table></figure>



<hr>
<p>💨 未完待续 ……</p>
<h2 id="支持亿点"><a href="#支持亿点" class="headerlink" title="支持亿点"></a>支持亿点</h2><p>🥕🐇🐇🐇</p>
<img src="wxpay.png" style="zoom:26%;" >

<p>💖</p>

        </section>
    </article>
</div>

            </div>
            <footer id="footer" class="footer">
    <div class="copyright">
        <span>187-9597-5517 &nbsp; 王鹏 @ <a href="https://cs.njupt.edu.cn/" target="_blank">njupt</a</span>
    </div>
</footer>

    </div>
</body>

</html>